Description

75. Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Constraints:

n == nums.length
1 <= n <= 300
nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Answer & Explaining

#include <stdio.h>

// 函式：sortColors，將陣列 nums 中的元素排序
void sortColors(int* nums, int numsSize) {
    // 初始化三個pointer：low、mid 和 high
    int low = 0, mid = 0, high = numsSize - 1;

    // 當 mid 小於或等於 high 時，持續迭代
    while (mid <= high) {
        // 若當前元素為 0
        if (nums[mid] == 0) {
            // 將 nums[low] 和 nums[mid] swap
            int temp = nums[low];
            nums[low] = nums[mid];
            nums[mid] = temp;
            // 將 low 和 mid pointer同時向右移動
            low++;
            mid++;
        // 若當前元素為 1
        } else if (nums[mid] == 1) {
            // 僅將 mid pointer向右移動
            mid++;
        // 若當前元素為 2
        } else {
            // 將 nums[mid] 和 nums[high] swap
            int temp = nums[mid];
            nums[mid] = nums[high];
            nums[high] = temp;
            // 將 high 指標向左移動
            high--;
        }
    }
}

Testing

#include <stdio.h>

// 函式：sortColors，將陣列 nums 中的元素排序
void sortColors(int* nums, int numsSize) {
    // 初始化三個pointer：low、mid 和 high
    int low = 0, mid = 0, high = numsSize - 1;

    // 當 mid 小於或等於 high 時，持續迭代
    while (mid <= high) {
        // 若當前元素為 0
        if (nums[mid] == 0) {
            // 將 nums[low] 和 nums[mid] swap
            int temp = nums[low];
            nums[low] = nums[mid];
            nums[mid] = temp;
            // 將 low 和 mid pointer同時向右移動
            low++;
            mid++;
        // 若當前元素為 1
        } else if (nums[mid] == 1) {
            // 僅將 mid pointer向右移動
            mid++;
        // 若當前元素為 2
        } else {
            // 將 nums[mid] 和 nums[high] swap
            int temp = nums[mid];
            nums[mid] = nums[high];
            nums[high] = temp;
            // 將 high 指標向左移動
            high--;
        }
    }
}

int main() {
    // 測試範例1：初始化陣列 nums1
    int nums1[] = {2, 0, 2, 1, 1, 0};
    int numsSize1 = sizeof(nums1) / sizeof(nums1[0]); // 計算 nums1 的長度
    sortColors(nums1, numsSize1); // 呼叫 sortColors 函式
    printf("Output for Example 1: "); 
    for (int i = 0; i < numsSize1; i++) {
        printf("%d ", nums1[i]); // 印出排序後的元素
    }
    printf("\n"); 

    // 測試範例2：初始化陣列 nums2
    int nums2[] = {2, 0, 1};
    int numsSize2 = sizeof(nums2) / sizeof(nums2[0]); // 計算 nums2 的長度
    sortColors(nums2, numsSize2); // 呼叫 sortColors 函式
    printf("Output for Example 2: "); 
    for (int i = 0; i < numsSize2; i++) {
        printf("%d ", nums2[i]); // 印出排序後的元素
    }
    printf("\n"); 

    return 0;
}